//给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否
//则返回 -1。 
//
// 
//示例 1: 
//
// 输入: nums = [-1,0,3,5,9,12], target = 9
//输出: 4
//解释: 9 出现在 nums 中并且下标为 4
// 
//
// 示例 2: 
//
// 输入: nums = [-1,0,3,5,9,12], target = 2
//输出: -1
//解释: 2 不存在 nums 中因此返回 -1
// 
//
// 
//
// 提示： 
//
// 
// 你可以假设 nums 中的所有元素是不重复的。 
// n 将在 [1, 10000]之间。 
// nums 的每个元素都将在 [-9999, 9999]之间。 
// 
// Related Topics 数组 二分查找 
// 👍 537 👎 0

package com.cute.leetcode.editor.cn;
public class BinarySearch {
    public static void main(String[] args) {
        Solution solution = new BinarySearch().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 使用二分法进行查找，数组有序且数组中元素不重复，这是使用二分的前提
         */
        public int search(int[] nums, int target) {
            int l = 0;
            int r = nums.length-1;
            int mid = 0;
            //这里定义未 <= 的话说明搜索区间是闭区间[l,r]，此时右边界是有用的
            //r的初始值也为len-1
            //这种定义方式我认为更好理解一些
            while (l<=r){
                mid = l + (r-l)/2;
                if (nums[mid] == target) return mid;
                else if (nums[mid] < target) l = mid+1;
                else r = mid-1;
            }


            //这里定义未 < 的话说明搜索区间是左闭右开区间[l,r)，此时右边界是没有用的
            //所以更新边界的时候 r = mid，而且r的初始值为len
            l = 0;
            r = nums.length;
            while (l<r){
                mid = l + (r-l)/2;
                if (nums[mid] == target) return mid;
                else if (nums[mid] < target) l = mid+1;
                else r = mid;
            }
            return -1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}